package Link;

import java.util.HashMap;
import java.util.Map;

public class leet_141 {
    public static void main(String[] args) {
        Solution_141 p = new Solution_141();
        ListNode resultNode = new ListNode(1);
        boolean result = p.hasCycle(resultNode);
        System.out.println(result);
    }
}


class Solution_141 {
    public boolean hasCycle(ListNode head) {
        boolean result = doubleCycle(head);
        return result;
    }

    /**
     * hash 判重法
     * @param head
     * @return
     */
    public boolean hashCycle(ListNode head){
        Map<ListNode, Integer> hashMap = new HashMap<>();
        while(head!=null){
            // 如果hash里面存在该节点
            if(hashMap.containsKey(head)){
                return true;
            }
            hashMap.put(head, 1);
            head = head.next;
        }
        return false;
    }


    /**
     * 快慢指针逻辑
     * 理论上不存在闭环的情况下
     * 直到快指针走完整个链表，慢指针的与快指针的关系都不相同
     * 但是 如果出现一个逻辑 环 慢指针一步一步走，总会与快指针
     * 在某一个点遇见那么代表这个链表存在环
     * @param head
     * @return
     */
    public boolean doubleCycle(ListNode head){
        if(head==null || head.next==null){
            // 单节点链表直接无重复
            return false;
        }
        // 快慢双指针
        ListNode slowNode = head;
        ListNode quickNode = head.next;

        while(slowNode!=quickNode){
            // 如果快指针能到头那么这个链表必然不存在环
            if(quickNode.next==null || quickNode.next.next==null){
                return false;
            }
            // 慢指针走一步，快指针走二步
            slowNode = slowNode.next;
            quickNode = quickNode.next.next;
        }
        return true;
    }


}